<html>
<head>
<title>Djkstra Algorithm</title>
<style type="text/css">
	#result {
		margin: 20px;
		background-color: 33FF66;
		color: black;
		font: bolder;
	}
</style>
<script type="text/javascript">
	var roads = {};
	var hasInitRoads = false;
	
	function forEach(array, action) {
		for (var i = 0; i < array.length; i++) {
			action(array[i]);
		}
	}
	
	function makeRoad(from, to, length) {
		function addRoad(from, to) {
			if (!(from in roads)) {
				roads[from] = [];
			}
			roads[from].push({
				to : to,
				distance : length
			});
		}
	
		addRoad(from, to);
		addRoad(to, from);
	}
	
	function makeRoads(start) {
		for ( var i = 1; i < arguments.length; i += 2)
			makeRoad(start, arguments[i], arguments[i + 1]);
	}
	
	function roadsFrom(place) {
		var toRoads = roads[place];
	
		if (toRoads == undefined) {
			throw new Error("No place named '" + place + "' found");
		}
	
		return toRoads;
	}
	
	// function gamblerPath(from, to) {
	// function randomInteger(below) {
	// return Math.floor(Math.random() * below);
	// }
	//	
	// function randomDirection(from) {
	// var options = roadsFrom(from);
	// return options[randomInteger(options.length)].to;
	// }
	//	
	// var path = [];
	// while (true) {
	// path.push(from);
	// if (from == to)
	// break;
	// from = randomDirection(from);
	// }
	// return path;
	// }
	
	function member(array, value) {
		var found = false;
		forEach(array, function(element) {
			if (element === value)
				found = true;
		});
		return found;
	}
	
	function filter(test, array) {
		var result = [];
		forEach(array, function(element) {
			if (test(element))
				result.push(element);
		});
		return result;
	}
	
	function flatten(arrays) {
		var result = [];
		forEach(arrays, function(array) {
			forEach(array, function(element) {
				result.push(element);
			});
		});
		return result;
	}
	
	function possibleRoutes(from, to) {
		function findRoutes(route) {
			function notVisited(road) {
				return !member(route.places, road.to);
			}
			function continueRoute(road) {
				return findRoutes({
					places : route.places.concat([ road.to ]),
					length : route.length + road.distance
				});
			}
	
			var end = route.places[route.places.length - 1];
			if (end == to)
				return [ route ];
			else
				return flatten(filter(notVisited, roadsFrom(end)).map(continueRoute));
		}
		return findRoutes({
			places : [ from ],
			length : 0
		});
	}
	
	function shortestRoute(from, to) {
		var currentShortest = null;
		forEach(possibleRoutes(from, to), function(route) {
			if (!currentShortest || currentShortest.length > route.length)
				currentShortest = route;
		});
		return currentShortest;
	}
	
	function initRoads() {
		makeRoads("A", "B", 6, "C", 3);
		makeRoads("B", "C", 2, "D", 5);
		makeRoads("C", "D", 3, "E", 4);
		makeRoads("D", "E", 2, "F", 3);
		makeRoads("E", "F", 5);
	}

	function $(elem) {
		return document.getElementById(elem);
	}
	
	function calculate() {
		if (!isInputValid()) {
			return;
		}
		if (!hasInitRoads)
			initRoads();
		
		var fromValue = $('from').value;
		var toValue = $('to').value;
		
		var sRoute = shortestRoute(fromValue, toValue);
		updateResultDiv(sRoute);
	}
	
	function updateResultDiv(shortestRoute) {
		var path = shortestRoute.places;
		var length = shortestRoute.length;
		var resultTxt = path + " (" + length + ") ";
		
		var resultDiv = document.createElement('div');
		var divIdName = 'result';
		resultDiv.setAttribute('id',divIdName);
		resultDiv.style.position = "relative";
		resultDiv.innerHTML = resultTxt;
		
		document.body.appendChild(resultDiv);
	}

	function isInputValid() {
		var fromValue = $('from').value;
		var toValue = $('to').value;
		if (isEmpty(fromValue) || isEmpty(toValue)) {
			alert("From or To can't be empty!");
			return false;
		}
		
		if (!isInRange(fromValue.toUpperCase()) || !isInRange(toValue.toUpperCase())) {
			alert("From: " + fromValue + " or To:" + toValue + " is not in A,B,C,D,E,F!");
			return false;
		}
		
		return true;
	}
	
	Array.prototype.contains = function(obj) {
	    var i = this.length;
	    while (i--) {
	        if (this[i] === obj) {
	            return true;
	        }
	    }
	    return false;
	}
	
	function isInRange(param) {
		var ranges = ['A', 'B', 'C', 'D', 'E', 'F'];
		
		if (ranges.contains(param)) {
			return true;
		}
		
		return false;
	}
	
	function isEmpty(param) {
		if (param == undefined || "" === param) {
			return true;
		}
		
		return false;
	}
</script>
</head>
<body>
	<h2>Djkstra Algorithm Javascript Implementation</h2>
	<div id="diagram">
		<img alt="dijkstra-diagram"
			src="http://img.blog.163.com/photo/WfZavQsDv8XkOKX7DnpGUg==/583497626721859365.jpg">
	</div>
	<p>
		From: <input type="text" id="from"> to: <input type="text"
			id="to"> <input type="button" value="calculate"
			onclick="calculate()">
	</p>
</body>
</html>